'''
https://leetcode.cn/problems/lexicographically-smallest-equivalent-string/?envType=study-plan-v2&envId=graph-theory
lexicographically: 辞典编纂的
'''

class UF:
    def __init__(self, n):
        self.father = list(range(n))
    def find(self, x):
        if x != self.father[x]:
            self.father[x] = self.find(self.father[x])
        return self.father[x]
    def is_same_set(self,x, y):
        return self.find(x) == self.find(y)
    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx < fy:
            self.father[fy] = fx
        elif fx > fy:
            self.father[fx] = fy

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        m, n = len(s1), len(baseStr)
        uf = UF(26)
        for i in range(m):
            a, b = ord(s1[i]) - ord('a'),  ord(s2[i]) - ord('a')
            uf.union(a, b)

        res = list(baseStr)
        for i in range(n):
            res[i] = chr(uf.find(ord(baseStr[i]) - ord('a')) + ord('a'))
        return ''.join(res)
